home *** CD-ROM | disk | FTP | other *** search
/ Day Cry / Day Cry CD.bin / oh_towns / taropyon / splib / splib.lzh / PRG / LHX / SLIDE.C < prev    next >
C/C++ Source or Header  |  1994-02-04  |  10KB  |  482 lines
  1. /***********************************************************
  2.         slide.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include    "lh386.h"
  5.  
  6. #include    <stdlib.h>
  7. #include    <string.h>             /* memmove() */
  8. #include    <dos.h>
  9. #include    "slidehuf.h"
  10. #include    "intrface.h"
  11.  
  12. #ifdef    __HIGHC__
  13. #    pragma    On(Print_reg_vars);
  14. #    pragma    On(Align_labels);
  15. #endif
  16.  
  17. #ifdef    __HIGHC__
  18. #    ifndef    PASCAL
  19. #        define    PASCAL    (_DEFAULT_CALLING_CONVENTION | _CALLEE_POPS_STACK)
  20. #    endif
  21. #endif
  22.  
  23. #ifdef    __HIGHC__
  24. #    pragma    Calling_convention(PASCAL);
  25. #endif
  26. static void init_slide(void);
  27. static node child(node q, uchar c);
  28. static void makechild(node q, uchar c, node r);
  29. static void split(node old);
  30. static void insert_node(void);
  31. static void delete_node(void);
  32. static void get_next_match(void);
  33. #ifdef    __HIGHC__
  34. #    pragma    Calling_convention();
  35. #endif
  36.  
  37.  
  38. #define PERCOLATE  1
  39. #define NIL        0
  40.  
  41. node       *next = NULL;
  42. int         unpackable = 0;
  43. ulong        origsize = 0, compsize = 0;
  44. ushort        dicbit = 0;
  45. ushort        maxmatch = 0;
  46. ulong        count = 0;
  47. ushort        loc = 0;
  48. uchar       *use_ptr = NULL;
  49.  
  50. uchar        text[TEXT_SIZE];
  51.  
  52. static struct encode_option encode_define[2] =
  53. {
  54. /* lh1     */    {             output_dyn, encode_start_fix, encode_end_dyn},
  55. /* lh4, 5 */    {(void (*)()) output_st1, encode_start_st1, encode_end_st1}
  56. };
  57.  
  58.  static struct decode_option decode_define[7] =
  59.  {
  60.  /* lh1 */     {decode_c_dyn, decode_p_st0, decode_start_fix},
  61.  /* lh2 */     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  62.  /* lh3 */     {decode_c_st0, decode_p_st0, decode_start_st0},
  63.  /* lh4 */     {decode_c_st1, decode_p_st1, decode_start_st1},
  64.  /* lh5 */     {decode_c_st1, decode_p_st1, decode_start_st1},
  65.  /* lzs */     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  66.  /* lz5 */     {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  67.  };
  68.  
  69.  static struct encode_option encode_set;
  70.  static struct decode_option decode_set;
  71.  
  72.  static node pos = 0, matchpos = 0, avail = 0,
  73.             *position = NULL, *parent = NULL, *prev = NULL;
  74.  static int  remainder = 0, matchlen = 0;
  75.  static uchar *level = NULL, *childcount = NULL;
  76.  static ushort dicsiz;
  77.  static ushort max_hash_val;
  78.  static ushort hash1, hash2;
  79.  
  80.  int         encode_alloc(int method)
  81. {
  82.     if (method == 1)
  83.     {
  84.         encode_set = encode_define[0];
  85.         maxmatch = 60;
  86.         dicbit = 12;
  87.     } else
  88.     {
  89.         encode_set = encode_define[1];
  90.         maxmatch = MAXMATCH;
  91.         dicbit = 13;
  92.     }
  93.     while (1)
  94.     {
  95.         dicsiz = 1U << dicbit;
  96.         max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  97.         level = malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  98.         childcount = malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  99. #if PERCOLATE
  100.         position = malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  101. #else
  102.         position = malloc(dicsiz * sizeof(*position));
  103. #endif
  104.         parent = malloc(dicsiz * 2 * sizeof(*parent));
  105.         prev = malloc(dicsiz * 2 * sizeof(*prev));
  106.         next = malloc((max_hash_val + 1) * sizeof(*next));
  107.         if (next == NULL ||
  108.             method > 1 && alloc_buf() == NULL)
  109.         {
  110.             if (next)
  111.                 free(next);
  112.             if (prev)
  113.                 free(prev);
  114.             if (parent)
  115.                 free(parent);
  116.             if (position)
  117.                 free(position);
  118.             if (childcount)
  119.                 free(childcount);
  120.             if (level)
  121.                 free(level);
  122.         } else
  123.         {
  124.             break;
  125.         }
  126.         if (--dicbit < 12)
  127.             error(MEMOVRERR, NULL);
  128.     }
  129.     if (method == 5)
  130.         method = dicbit - 8;
  131.     return method;
  132. }
  133.  
  134. static void init_slide(void)
  135. {
  136.     node        i;
  137.  
  138.     for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++)
  139.     {
  140.         level[i] = 1;
  141. #if PERCOLATE
  142.         position[i] = NIL;        /* sentinel */
  143. #endif
  144.     }
  145.     for (i = dicsiz; i < dicsiz * 2; i++)
  146.         parent[i] = NIL;
  147.     avail = 1;
  148.     for (i = 1; i < dicsiz - 1; i++)
  149.         next[i] = i + 1;
  150.     next[dicsiz - 1] = NIL;
  151.     for (i = dicsiz * 2; i <= max_hash_val; i++)
  152.         next[i] = NIL;
  153.     hash1 = dicbit - 9;
  154.     hash2 = dicsiz * 2;
  155. }
  156.  
  157. #define HASH(p, c) ((p) + ((c) << hash1) + hash2)
  158.  
  159. static node child(node q, uchar c)
  160. /* q's child for character c (NIL if not found) */
  161. {
  162.     node        r;
  163.  
  164.     r = next[HASH(q, c)];
  165.     parent[NIL] = q;            /* sentinel */
  166.     while (parent[r] != q)
  167.         r = next[r];
  168.     return r;
  169. }
  170.  
  171. static void makechild(node q, uchar c, node r)
  172. /* Let r be q's child for character c. */
  173. {
  174.     node        h, t;
  175.  
  176.     h = HASH(q, c);
  177.     t = next[h];
  178.     next[h] = r;
  179.     next[r] = t;
  180.     prev[t] = r;
  181.     prev[r] = h;
  182.     parent[r] = q;
  183.     childcount[q]++;
  184. }
  185.  
  186. static void split(node old)
  187. {
  188.     node        new, t;
  189.  
  190.     new = avail;
  191.     avail = next[new];
  192.     childcount[new] = 0;
  193.     t = prev[old];
  194.     prev[new] = t;
  195.     next[t] = new;
  196.     t = next[old];
  197.     next[new] = t;
  198.     prev[t] = new;
  199.     parent[new] = parent[old];
  200.     level[new] = matchlen;
  201.     position[new] = pos;
  202.     makechild(new, text[matchpos + matchlen], old);
  203.     makechild(new, text[pos + matchlen], pos);
  204. }
  205.  
  206. static void insert_node(void)
  207. {
  208.     node        q, r, j, t;
  209.     uchar        c, *t1, *t2;
  210.  
  211.     if (matchlen >= 4)
  212.     {
  213.         matchlen--;
  214.         r = (matchpos + 1) | dicsiz;
  215.         while ((q = parent[r]) == NIL)
  216.             r = next[r];
  217.         while (level[q] >= matchlen)
  218.         {
  219.             r = q;
  220.             q = parent[q];
  221.         }
  222. #if PERCOLATE
  223.         t = q;
  224.         while (position[t] < 0)
  225.         {
  226.             position[t] = pos;
  227.             t = parent[t];
  228.         }
  229.         if (t < dicsiz)
  230.             position[t] = pos | 0x8000;
  231. #else
  232.         t = q;
  233.         while (t < dicsiz)
  234.         {
  235.             position[t] = pos;
  236.             t = parent[t];
  237.         }
  238. #endif
  239.     } else
  240.     {
  241.         q = text[pos] + dicsiz;
  242.         c = text[pos + 1];
  243.         if ((r = child(q, c)) == NIL)
  244.         {
  245.             makechild(q, c, pos);
  246.             matchlen = 1;
  247.             return;
  248.         }
  249.         matchlen = 2;
  250.     }
  251.     for (;;)
  252.     {
  253.         if (r >= dicsiz)
  254.         {
  255.             j = maxmatch;
  256.             matchpos = r;
  257.         } else
  258.         {
  259.             j = level[r];
  260.             matchpos = position[r] & 0x7fff;
  261.         }
  262.         if (matchpos >= pos)
  263.             matchpos -= dicsiz;
  264.         t1 = &text[pos + matchlen];
  265.         t2 = &text[matchpos + matchlen];
  266.         while (matchlen < j)
  267.         {
  268.             if (*t1 != *t2)
  269.             {
  270.                 split(r);
  271.                 return;
  272.             }
  273.             matchlen++;
  274.             t1++;
  275.             t2++;
  276.         }
  277.         if (matchlen == maxmatch)
  278.             break;
  279.         position[r] = pos;
  280.         q = r;
  281.         if ((r = child(q, *t1)) == NIL)
  282.         {
  283.             makechild(q, *t1, pos);
  284.             return;
  285.         }
  286.         matchlen++;
  287.     }
  288.     t = prev[r];
  289.     prev[pos] = t;
  290.     next[t] = pos;
  291.     t = next[r];
  292.     next[pos] = t;
  293.     prev[t] = pos;
  294.     parent[pos] = q;
  295.     parent[r] = NIL;
  296.     next[r] = pos;                /* special use of next[] */
  297. }
  298.  
  299. static void delete_node(void)
  300. {
  301. #if PERCOLATE
  302.     node        q, r, s, t, u;
  303. #else
  304.     node        r, s, t, u;
  305. #endif
  306.  
  307.     if (parent[pos] == NIL)
  308.         return;
  309.     r = prev[pos];
  310.     s = next[pos];
  311.     next[r] = s;
  312.     prev[s] = r;
  313.     r = parent[pos];
  314.     parent[pos] = NIL;
  315.     if (r >= dicsiz || --childcount[r] > 1)
  316.         return;
  317. #if PERCOLATE
  318.     t = position[r] & 0x7fff;
  319. #else
  320.     t = position[r];
  321. #endif
  322.     if (t >= pos)
  323.         t -= dicsiz;
  324. #if PERCOLATE
  325.     s = t;
  326.     q = parent[r];
  327.     while ((u = position[q]) < 0)
  328.     {
  329.         u &= 0x7fff;
  330.         if (u >= pos)
  331.             u -= dicsiz;
  332.         if (u > s)
  333.             s = u;
  334.         position[q] = (s | dicsiz);
  335.         q = parent[q];
  336.     }
  337.     if (q < dicsiz)
  338.     {
  339.         if (u >= pos)
  340.             u -= dicsiz;
  341.         if (u > s)
  342.             s = u;
  343.         position[q] = (s | dicsiz) | 0x8000;
  344.     }
  345. #endif
  346.     s = child(r, text[t + level[r]]);
  347.     t = prev[s];
  348.     u = next[s];
  349.     next[t] = u;
  350.     prev[u] = t;
  351.     t = prev[r];
  352.     next[t] = s;
  353.     prev[s] = t;
  354.     t = next[r];
  355.     prev[t] = s;
  356.     next[s] = t;
  357.     parent[s] = parent[r];
  358.     parent[r] = NIL;
  359.     next[r] = avail;
  360.     avail = r;
  361. }
  362.  
  363. static void get_next_match(void)
  364. {
  365.     int         n;
  366.  
  367.     remainder--;
  368.     if (++pos == dicsiz * 2)
  369.     {
  370.         memmove(&text[0], &text[dicsiz], dicsiz + maxmatch);
  371.         n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
  372.         remainder += n;
  373.         pos = dicsiz;
  374.     }
  375.     delete_node();
  376.     insert_node();
  377. }
  378.  
  379. void        encode(struct interfacing * interface)
  380. {
  381.     int         lastmatchlen, dicsiz1;
  382.     node        lastmatchpos;
  383.  
  384.     infile = interface->infile;
  385.     outfile = interface->outfile;
  386.     origsize = interface->original;
  387.     dispflg = interface->dispflg;
  388.     compsize = 0;
  389.     crc = unpackable = 0;
  390.     init_slide();
  391.     encode_set.encode_start();
  392.     dicsiz1 = dicsiz - 1;
  393.     pos = dicsiz + maxmatch;
  394.     memset(&text[pos], ' ', dicsiz);
  395.     remainder = fread_crc(&text[pos], dicsiz, infile);
  396.     matchlen = 0;
  397.     insert_node();
  398.     if (matchlen > remainder)
  399.         matchlen = remainder;
  400.     while (remainder > 0 && !unpackable)
  401.     {
  402.         lastmatchlen = matchlen;
  403.         lastmatchpos = matchpos;
  404.